problem

輸入為一個二元樹，如果一個節點的深度代表節點到根節點的距離，回傳二元樹中所有節點的深度總和。

二元樹如下結構，每一個 BinaryTree 節點有一個整數值 value，左子節點 left，右子節點 right。子節點可能為其他 BinaryTree 節點或為空值。

class BinaryTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

sample input:
  tree = 1
     /  \
    2   3
    /  \  /  \
   4    5  6  7
    /  \
   8    9
sample output:
16
// 節點 2、3 的深度為 1
// 節點 4、5、6、7 的深度為 2
// 節點 8、9 的深度為 3

這題基本的想法是，如果只單獨看樹中的任一節點，無上下節點的連結，其實無法知道它在樹中的深度，所以要知道任一節點深度，必然要從根節點開始，逐層將深度加一，傳給子節點做計算。實作上可以分為以下兩種寫法。

solution 01

第一種是遞迴寫法，也就是函式在每一個節點回傳當前節點的深度，並且對子節點呼叫遞迴式，最終回傳所有深度總和。

以虛擬碼大致可以寫成：

// d 代表深度
f(node, d) = d + f(left, d + 1) + f(right, d + 1)

若 n 為二元樹中的節點數量，h 為樹的高度，
time: O(n)
space: O(h) 因為遍歷節點的過程中，每一層會呼叫一次遞迴式。若是結構平衡的二元樹，也可以表達為 O(logn)。

function nodeDepths(root, depth = 0) {
  if (root === null) return 0;
  return depth + nodeDepths(root.left, depth + 1) + nodeDepths(root.right, depth + 1);
}

solution 02

第二種是利用堆疊結構進行疊代的寫法。
步驟是：

1. 將根節點和其深度加入堆疊中。
2. 只要堆疊不為空，將節點移除，移除時，若該節點不為空，將深度加入總和之中，並將該節點的子節點和深度加入堆疊中。若移除時節點為空則不做任何操作。
3. 最終回傳總和。

這種解的時間和空間複雜度跟第一種解法相同，時間的部分因為一樣遍歷過每個節點，空間的部分則是來自堆疊。如果以上方的 sample input 進行這種解法，堆疊中節點的變化大致如下：

            8
        4   9   9
    2   5   5   5   5
1 → 3 → 3 → 3 → 3 → 3 → 3 ....// 剩下節點以此類推

此處每次移除節點時，都先將右邊子節點加入堆疊中，實際操作時先加入左邊或右邊子節點沒有影響，只是由此範例可以看出堆疊最多儲存的節點數量約等於樹的高度。

function nodeDepths(root) {
  let sumOfDepths = 0;
  const stack = [{ node: root, depth: 0 }];
  while (stack.length > 0) {
    const { node, depth } = stack.pop();
    if (node === null) continue;
    sumOfDepths += depth;
    stack.push({ node: node.right, depth: depth + 1 });
    stack.push({ node: node.left, depth: depth + 1 });
  }
  return sumOfDepths;
}